package master;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chenyw
 * @date 2022/9/8 19:58
 * 组合总数III
 */
public class M216combinationSum3 {
    static List<List<Integer>> res = new ArrayList<>();

    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum3(2, 18);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
    public static List<List<Integer>> combinationSum3(int k, int n) {
        dfs(n, 1, k, 0, new ArrayList<Integer>());
        return res;
    }

    private static void dfs(int n, int start, int k, int sum, ArrayList<Integer> list) {
        if (sum == n && list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }
        if (sum > n || list.size() > n) {
            return;
        }
        for (int i = start; i < 10; i++) {
            sum += i;
            list.add(i);
            dfs(n, i + 1, k, sum, list);
            sum -= i;
            list.remove(list.size() - 1);
        }
    }
}
